package com.zlk.algorithm.algorithm.recursion;

import org.junit.Test;

/**
 * @program: algorithm
 * @ClassName FindBigestValInarr
 * @description:用递归行为得到数组中的最大值，并用master公式来估计时间复杂度
 * @author: slfang
 * @create: 2024-01-02 13:56
 * @Version 1.0
 **/
public class FindBigestValInarr {

    @Test
    public void test(){
        int testTimes = 10000;
        int limitArrVal = 100;
        int limitArrLength = 5;
        for (int i = 0; i < testTimes; i++) {
            int[] randomArr = getRandomArr(limitArrLength, limitArrVal);
            int i1 = testBigValInArr(randomArr);
            int bigestValInarr = findBigestValInarr(randomArr);
            if(i1!=bigestValInarr){
                System.out.println("执行失败");
                System.out.println("test:"+i1);
                System.out.println("bigestValInarr:"+bigestValInarr);
                return ;
            }
        }
        System.out.println("success");
    }

    private int testBigValInArr(int[] randomArr) {
        int maxVal=Integer.MIN_VALUE;
        for (int val : randomArr) {
            if(val>maxVal){
                maxVal = val;
            }
        }
        return maxVal;
    }

    private int[] getRandomArr(int limitArrLength, int limitArrVal) {
        int length =(int)(Math.random()*(limitArrLength+1));
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            int number = randomNumber(limitArrVal);
            arr[i] = number;
        }
        return arr;
    }

    // [-range, +range]
    public static int randomNumber(int range) {
        return (int) (Math.random() * (range + 1)) - (int) (Math.random() * (range + 1));
    }

    private int findBigestValInarr(int[] arr) {
        return bigestValInarr(arr,0,arr.length-1);

    }

    private int bigestValInarr(int[] arr, int l, int r) {
        if(l == r){ return arr[l];}
        int mid = l+((r-l)>>1);
        return Math.max(bigestValInarr(arr,l,mid),bigestValInarr(arr,mid+1,r));
    }


}
